import java.util.*;

public class Test {


    public static void main1(String[] args) {
        String s = new String("A man, a plan, a canal: Panama");
        Test test = new Test();
        System.out.println(test.isPalindrome2(s));
    }

    /**
     * 使用栈  队列  解决回文串
     * @param s
     * @return
     */
    public boolean isPalindrome(String s) {
        Queue<Integer> queue = new LinkedList<>();
        Stack<Integer> stack = new Stack<>();
        s = s.toLowerCase();
        for(int i = 0;i < s.length();i++) {
            char tmp = s.charAt(i);
            if(( tmp>= 'a' && tmp <= 'z')
                    || (tmp >= 48 && tmp <= 57)) {
                queue.offer((int)tmp);
                stack.push((int)tmp);
            }
        }
        for(int i = 0;i < queue.size();i++) {
            if(queue.poll() != stack.pop()) {
                return false;
            }
        }
        return true;
    }

    /**
     * 使用StringBuilder解决回文串
     * @param s
     * @return
     */
    public boolean isPalindrome2(String s) {
        s = s.toLowerCase();
        StringBuilder tmp = new StringBuilder();
        int length = s.length();
        for(int i = 0; i < length; i++) {
            char ss = s.charAt(i);
            if(ss >= 'a' && ss <= 'z' ||(ss >= 48 && ss <= 57)) {
                tmp.append(ss);
            }
        }
        StringBuilder tmpPalindrome = new StringBuilder(tmp.reverse());
        tmp.reverse();
        return tmp.toString().equals(tmpPalindrome.toString());
    }
    public List<List<Integer>> generate(int numRows) {
        List<List<Integer>> dp = new ArrayList<List<Integer>>();
        //初始化边界

        for(int i = 0; i < numRows; i++) {
            List<Integer> tmp = new ArrayList<>();
            for(int j = 0;j <= i;j++) {
                if(j == 0 || i == j) {
                    tmp.add(1);
                }else {
                    tmp.add(dp.get(i-1).get(j) + dp.get(i-1).get(j-1));
                }

            }
            dp.add(tmp);
        }
        return dp;
    }
    public String longestPalindrome(String s) {
        int len = s.length();
        Map<Integer,String> map = new TreeMap<>();
        for(int i = 0;i <= len;i++) {
            for(int j = len;j >= i;j--) {
                if(Palindrome(s.substring(i,j))) {
                    map.put(s.substring(i,j).length(),s.substring(i,j));
                }
            }
        }
        for(int i = len;i >= 0;i--) {
            if(map.containsKey(i)) {
                return map.get(i);
            }
        }
        return null;
    }
    public boolean Palindrome(String ss) {
        StringBuilder tmp = new StringBuilder(ss);
        StringBuilder tmpPalindrome = new StringBuilder(tmp.reverse());
        tmp.reverse();
        return tmp.toString().equals(tmpPalindrome.toString());
    }
    public boolean Palindrome2(String ss) {
        char[] array = ss.toCharArray();
        int left = 0;
        int right = array.length-1;
        while(left < right) {
            if(array[left] != array[right]) {
                return false;
            }
            left++;
            right--;
        }
        return true;
    }

    public static void main(String[] args) {
        String ss = new String("ababababaababababababababa");
        Test test = new Test();
        //System.out.println(test.longestPalindrome(ss));
        System.out.println(test.Palindrome2(ss));
    }
}
